/**
 * 875. 爱吃香蕉的珂珂
 * https://leetcode-cn.com/problems/koko-eating-bananas/
 */
public class Solutions_875 {
    public static void main(String[] args) {
//        int[]  piles = {3, 6, 7, 11};
//        int H = 8;  // output:  4

//        int[]  piles = {30, 11, 23, 4, 20};
//        int H = 5;  // output:  30

        int[] piles = {30, 11, 23, 4, 20};
        int H = 6;  // output:  23

        int result = minEatingSpeed(piles, H);
        System.out.println(result);
    }

    public static int minEatingSpeed(int[] piles, int H) {
        // 找到 piles 数组的最大值 b，那么按每小时吃 b 个香蕉的话，一定可以在 H 小时内吃完
//        int max = 0;
//        for (int num : piles) {
//            max = Math.max(max, num);
//        }
        // 直接定义 max，减少了遍历 num 查找最大值的过程
        int max = 1_000_000_000;
        int min = 1;
        while (min <= max) {
            // 二分查找
            int mid = min + (max - min) / 2;
            // 判断每小时 mid 根香蕉的速度，能否吃完
            boolean flag = isFinish(piles, mid, H);
            if (flag) {
                // 可以吃完，那么将 mid 缩小，判断是否还是可以（因为要查找最小的速度）
                max = mid - 1;
            } else {
                // 速度过慢，无法吃完，那么将 mid 扩大
                min = mid + 1;
            }
        }
        // 最终 min 即是可以完成的最慢速度
        return min;
    }

    public static boolean isFinish(int[] piles, int speed, int H) {
        int count = 0;
        for (int num : piles) {
            // 需要向上取整
//            count += Math.ceil(num / (speed * 1.0));
            count += (num - 1) / speed + 1;
            if (count > H) {
                // 提前返回：无法在 H 小时内吃完
                return false;
            }
        }
        return true;
    }
}
